1. Field of the Invention
This invention relates to congestion within a computer network, and more particularly to avoidance of congestion.
2. Background Information
Modern network devices, layer 3 routers, layer 2 switches, etc., are designed with linecards interfacing to the computer network, and with a switching fabric interconnecting the linecards inside the network device. As packets arrive at the linecards, typically IP packets, from the computer network, they are converted into fixed length packets referred to as “segments” and forwarded to the switching fabric. A frequently used fixed length packet is the Asynchronous Transfer Mode (ATM) cell, and the switching fabric then used is an ATM based switching fabric. Also, various vendors use other segment types, for example a 64 byte, or a 128 byte, or a 256 byte, etc., segment are sometimes employed. The design of a segment, or cell, switching fabric is described in the Stanford University project “Tiny-Tera” in documents found at the website: http://klamath.stanford.edu/tiny-tera.
The switching fabric routes the segments to the proper output linecard. The output linecard converts the sequence of segments into the proper format packet to transmit onto the output computer network connected to the output linecard, and transmits the packet onto the output computer network.
The switching fabric has queues internal to its structure. As these queues fill up from heavy traffic loads on the network device, segments can be dropped by the switching fabric. The output linecard then receives a defective packet, and does not transmit the defective packet. The switching fabric does not “see” packets, it only handles segments. Thus it becomes the job of the output linecard to drop a defective packet.
When a packet is dropped, the destination computer does not receive the packet, and consequently does not transmit an Acknowledgement (ACK) message to the source computer. A timer in the source computer (retransmit timer) which is waiting for receipt of the ACK message times out, causing the source station to transmit a replacement packet. The replacement packet contributes to the already congested situation within the switching fabric. A source computer implementing TCP/IP, or some other adaptable protocol, reduces the rate at which it transmits packets in response to its retransmit timer timing out. As segments are lost within the congested switching fabric (and consequently packets headed toward the destination computer are lost), a source computer using an adaptable protocol such as TCP transmits at slower and slower transmission rates. Slow transmission rates may underutilize links of the network, resulting in wasted bandwidth in the network.
As filled queues within the switch fabric overflow and segments are dropped, many packets from many different source stations may be dropped. These source stations will then transmit their replacement packets at nearly the same time, thereby creating undesirable network synchronization. The replacement packets will then all reach the network device at about the same time, and contribute even more to congestion within the network device.
An algorithm, referred to as the Random Early Detection (RED) algorithm uses direct measurement of queue length to randomly drop a computer network packet, is described by S. Floyd and V. Jacobson in the paper “Random Early Detection Gateways for Congestion Avoidance”, published in IEEE/ACM Transactions on Networking, V. 1, N4, p. 397-412, in August 1993, all disclosures of which are incorporated herein by reference. Also, further features of the RED algorithm are described in the paper by V. Jacobson, K. Nichols, K. Poduri, titled “RED in A New Light”, unpublished but widely circulated, all disclosures of which are incorporated herein by reference. However, when a switching fabric implemented in a commercial set of computer chips is used in a network device, there is no way to access queue lengths by the designer of the network device and so no way to implement the RED algorithm.
There is needed a method for detecting the fact that incipient congestion is building within a switching fabric of a network device, where access to queue length is not available to the designer of the network device, and to respond to the incipient congestion by dropping a packet before congestion becomes severe.